package org.rudenko.sort;

import java.util.ArrayList;

public class ShellSort{
	public int array[];
	private static ArrayList<Integer> increments(int s){
		ArrayList<Integer> d = new ArrayList<Integer>();
		int i=0;
		do{
			if (i%2==1){
				d.add(8*(int)Math.pow(2, i)-6*(int)Math.pow(2,(i+1)/2)+1);	
			}else{			
				d.add(9*(int)Math.pow(2, i)-9*(int)Math.pow(2,i/2)+1);
			}
			i++;
		}while(3*d.get(i-1) < s);
		return d;
	}
	
	public  ShellSort(int[] array){
		int l=array.length;
		int buf;
		ArrayList<Integer> d = increments(l);
		for(int s=d.size()-1;s>=0;s--){

			for (int i=0;i<l;i=i+d.get(s)){
				for (int j=0;j<l;j=j+d.get(s)){
					if(array[i] < array[j]){						
						buf=array[i];
						array[i]=array[j];
						array[j]=buf;
					}
				}
			}
		}
		
	}
	
	public int[] getSortedArray(){
		return array;	
	}

}
